package ch04;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

//有向图基于DFS的顶点排序
//拓扑排序就是有向无环图的逆后序排序
public class DepthFirstOrder {
    private boolean[] marked;
    private Queue<Integer> pre;
    private Queue<Integer> post;
    private Stack<Integer> reversePost;

    public DepthFirstOrder(DiGraph graph) {
        int v = graph.V();
        marked = new boolean[v];
        post = new LinkedList<Integer>();
        pre = new LinkedList<Integer>();
        reversePost = new Stack<>();
        for (int i = 0; i < v; i++) {
            if (!marked[i]) {
                DFS(graph, i);
            }
        }
    }

    public void DFS(DiGraph graph, int v) {

        marked[v] = true;
        pre.offer(v);
        for (Integer w : graph.adj(v)) {
            if(!marked[w])
                DFS(graph, w);
        }
        post.offer(v);
        reversePost.push(v);
    }

    public Queue<Integer> getPre(){
        return pre;
    }

    public Queue<Integer> getPost() {
        return post;
    }

    public Stack<Integer> getReversePost() {
        return reversePost;
    }

    public static void main(String[] args) {
        DiGraph digGraph = DiGraph.getDigGraph();
        DepthFirstOrder dfo = new DepthFirstOrder(digGraph);
        Queue<Integer> pre = dfo.getPre();
        for (Integer integer : pre) {
            System.out.println(integer);
        }
        Queue<Integer> post = dfo.getPost();
        Stack<Integer> reversePost = dfo.getReversePost();


    }
}
